// https://leetcode.cn/problems/kth-smallest-element-in-a-bst/

// 题干：给定一个二叉搜索树的根节点 root， 和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

// 示例：输入：root = [3,1,4,null,2], k = 1
//       输出：1

// 碎语：二叉搜索树的中序遍历的结果是一个有序数列
//       善用全局变量，能减少参数个数，构造好的返回值

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
    int ret;
    int count;
public:
    int kthSmallest(TreeNode* root, int k)
    {
        count = k;
        dfs(root);

        return ret;
    }

    void dfs(TreeNode* root)
    {
        if (root == nullptr || count == 0) return ; // 剪枝

        dfs (root->left);
        count--;
        if (count == 0) ret = root->val;

        dfs(root->right);
    }
};

int main()
{
    Solution sol;

    auto root = new TreeNode(3);
    root->left = new TreeNode(1);
    root->right = new TreeNode(4);
    root->left->right = new TreeNode(2);

    cout << sol.kthSmallest(root, 1) << " ";

    return 0;
}